package com.leecode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 198. 打家劫舍
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 * 示例 1：
 * 输入：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 * 偷窃到的最高金额 = 1 + 3 = 4 。
 * <p>
 * 实际:这就是面试中的"取不相邻石头的max"的变种
 */
public class Leet198 {
	public static void main(String[] args) {

	}

	Map<Integer, Integer> map = new HashMap();

	public int rob(int[] nums) {
		if (nums.length == 0) return 0;
		if (nums.length <= 2)
			return Math.max(nums[0], nums[nums.length - 1]);

		int[] temp = Arrays.copyOf(nums, nums.length - 2);
		int[] temp2 = Arrays.copyOf(nums, nums.length - 3);
		if (map.containsKey(nums.length)) return map.get(nums.length);
		int result = Math.max(nums[nums.length - 2] + rob(temp2), nums[nums.length - 1] + rob(temp));
		map.put(nums.length, result);
		return result;
	}


	/**
	 * 考点:max(i)=max(i+max(i-2),max(i-1)),这么分析出来后,很明显是dp
	 */
	public int rob2(int[] nums) {
		if(nums.length==0)return 0;
		if (nums.length == 1) return nums[0];
		if (nums.length == 2) return Math.max(nums[0], nums[1]);

		int[] dp = new int[nums.length];
		dp[0] = nums[0];
		dp[1] = Math.max(nums[0], nums[1]);
		for (int a = 2; a < nums.length; a++) {
			dp[a] = Math.max(nums[a] + dp[a - 2], dp[a - 1]);
		}
		return dp[nums.length - 1];
	}

	//100%,80%
	public int rob3(int[] nums) {
		if(nums.length==0)return 0;
		if (nums.length == 1) return nums[0];
		if (nums.length == 2) return Math.max(nums[0], nums[1]);

		int pre = nums[0];
		int aft = Math.max(nums[0], nums[1]);
		for (int a = 2; a < nums.length; a++) {
			int temp = Math.max(nums[a] + pre, aft);
			pre=aft;
			aft=temp;
		}
		return aft;
	}

}
